// --------------------------------------------------------------------------------------------------------------------
// <copyright file="HashMap.cs" company="JDML Consulting Ltd.">
//   Copyright 2011 Photon Project - http://photon.codeplex.com
// </copyright>
// <summary>
//   Hashmap
// </summary>
// --------------------------------------------------------------------------------------------------------------------

namespace Photon.Collections
{
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Threading;

    public partial class HashMap<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary
    {
        #region Fields

        private IEqualityComparer<TKey> _equalityComparer;
        private KeyCollection _keys;
        private object _syncRoot;
        private Entry[] _buckets;
        private ValueCollection _values;
        private int _version;

        #endregion

        #region Consts

        /// <summary>
        /// The default load factor for the HashMap class.
        /// </summary>
        public const double DefaultLoadFactor = 0.8F;

        #endregion

        #region Nested Types

        #region Entry

        /// <summary>
        /// Abstract base Entry class.
        /// </summary>
        public abstract class Entry
        {
            /// <summary>
            /// The next.
            /// </summary>
            internal Entry Next;

            /// <summary>
            /// Gets the key.
            /// </summary>
            /// <value>The key.</value>
            public abstract TKey Key { get; }

            /// <summary>
            /// Gets or sets the value.
            /// </summary>
            /// <value>The value.</value>
            public abstract TValue Value { get; set; }

            /// <summary>
            /// Gets a value indicating whether this instance is alive.
            /// </summary>
            /// <value><c>true</c> if this instance is alive; otherwise, <c>false</c>.</value>
            public virtual bool IsAlive { get { return true; } }
        }

        #endregion

        #region DefaultEntry

        /// <summary>
        /// Default entry
        /// </summary>
        private class DefaultEntry : Entry
        {
            #region Fields

            /// <summary>
            /// The _key.
            /// </summary>
            private readonly TKey _key;

            /// <summary>
            /// The _value.
            /// </summary>
            private TValue _value;

            #endregion

            /// <summary>
            /// Initializes a new instance of the <see cref="HashMap&lt;TKey, TValue&gt;.DefaultEntry"/> class.
            /// </summary>
            /// <param name="key">
            /// The key.
            /// </param>
            /// <param name="value">
            /// The value.
            /// </param>
            public DefaultEntry(TKey key, TValue value)
            {
                _key = key;
                _value = value;
            }

            /// <summary>
            /// Gets the key.
            /// </summary>
            /// <value>The key.</value>
            public override TKey Key
            {
                get { return _key; }
            }

            /// <summary>
            /// Gets or sets the value.
            /// </summary>
            /// <value>The value.</value>
            public override TValue Value
            {
                get { return _value; }
                set { _value = value; }
            }
        }

        #endregion

        #endregion

        /// <summary>
        /// Initializes a new instance of the <see cref="HashMap{TKey,TValue}"/> class. 
        /// Initialises a new instance of the HashMap class.
        /// </summary>
        public HashMap()
            : this(0, DefaultLoadFactor, null)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="HashMap{TKey,TValue}"/> class.
        /// Initialises a new instance of the HashMap class.
        /// </summary>
        /// <param name="initialCapacity">The initial capacity.</param>
        public HashMap(int initialCapacity)
            : this(initialCapacity, DefaultLoadFactor, null)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="HashMap{TKey,TValue}"/> class.
        /// </summary>
        /// <param name="initialCapacity">The initial capacity.</param>
        /// <param name="loadFactor">The load factor.</param>
        public HashMap(int initialCapacity, double loadFactor)
            : this(initialCapacity, loadFactor, null)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="HashMap{TKey,TValue}"/> class. 
        /// Initializes a new instance of the <see cref="HashMap&lt;TKey, TValue&gt;"/> class.
        /// </summary>
        /// <param name="dictionary">
        /// The dictionary.
        /// </param>
        public HashMap(IDictionary<TKey, TValue> dictionary)
            : this(dictionary, null, DefaultLoadFactor)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="HashMap{TKey,TValue}"/> class. 
        /// </summary>
        /// <param name="dictionary">The dictionary.</param>
        /// <param name="equalityComparer">The equality comparer.</param>
        /// <param name="loadFactor">The load factor.</param>
        public HashMap(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> equalityComparer, double loadFactor)
            : this((dictionary != null) ? dictionary.Count : 0, loadFactor, equalityComparer)
        {
            // Add from the dictionary 
            InternalAdd(dictionary);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="HashMap{TKey,TValue}"/> class. 
        /// Initialises a new instance of the HashMap class.
        /// </summary>
        /// <param name="initialCapacity">
        /// The initial capacity.
        /// </param>
        /// <param name="loadFactor">
        /// The load factor.
        /// </param>
        /// <param name="equalityComparer">
        /// The equality comparer.
        /// </param>
        public HashMap(int initialCapacity, double loadFactor, IEqualityComparer<TKey> equalityComparer)
        {
            #region Validation Arguments

            if (loadFactor < 0.1)
            {
                throw new ArgumentException("Value cannot be less than 0.1.", "loadFactor");
            }

            if (loadFactor > 1.0)
            {
                throw new ArgumentException("Value cannot be greater than 1.0.", "loadFactor");
            }

            if (initialCapacity < 0)
            {
                throw new ArgumentException("Value cannot be less than 0.", "initialCapacity");
            }

            #endregion

            ResetCapacity(initialCapacity);
            LoadFactor = loadFactor;
            EqualityComparer = equalityComparer ?? EqualityComparer<TKey>.Default;
        }

        /// <summary>
        /// Gets or sets the <see cref="IEqualityComparer{T}"/> for the HashMap.
        /// </summary>
        /// <value>The equality comparer.</value>
        /// <remarks>
        /// By default the dictionary compares keys using <see cref="EqualityComparer{T}.Default"/>.
        /// </remarks>
        public IEqualityComparer<TKey> EqualityComparer
        {
            get
            {
                return _equalityComparer;
            }
            set
            {
                Guard.ArgumentNull("value", value);
                if (_equalityComparer != value)
                {
                    _equalityComparer = value;
                    if (Count != 0)
                    {
                        Rehash(Capacity, LoadFactor);
                    }
                }
            }
        }

        /// <summary>
        /// Gets the capacity of the HashMap.
        /// </summary>
        /// <remarks>
        /// The capacity refers to the number of slots, or hash buckets the HashMap has 
        /// available. Capacity is automatically increased as required based on 
        /// the load factor.
        /// </remarks>
        public int Capacity
        {
            get { return this._buckets.Length; }
        }

        /// <summary>
        /// Gets the load factor for the HashMap.
        /// </summary>
        public double LoadFactor { get; private set; }

        #region IDictionary Members

        /// <summary>
        /// Gets a value indicating whether this instance is fixed size.
        /// </summary>
        /// <value><c>true</c> if this instance is fixed size; otherwise, <c>false</c>.
        /// </value>
        public virtual bool IsFixedSize
        {
            get { return false; }
        }

        /// <summary>
        /// Gets a value indicating whether this instance is synchronized.
        /// </summary>
        /// <value><c>true</c> if this instance is synchronized; otherwise, <c>false</c>.</value>
        public bool IsSynchronized
        {
            get { return false; }
        }

        /// <summary>
        /// Gets the sync root.
        /// </summary>
        /// <value>The sync root.</value>
        public object SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                {
                    Interlocked.CompareExchange(ref _syncRoot, new object(), null);
                }

                return _syncRoot;
            }
        }

        /// <summary>
        /// Gets Values.
        /// </summary>
        ICollection IDictionary.Values
        {
            get { return _values ?? (_values = new ValueCollection(this)); }
        }

        /// <summary>
        /// The remove.
        /// </summary>
        /// <param name="key">
        /// The key.
        /// </param>
        void IDictionary.Remove(object key)
        {
            Guard.ArgumentNull("key", key);
            if (key is TKey)
            {
                this.Remove((TKey)key);
            }
        }

        /// <summary>
        /// The i dictionary.this.
        /// </summary>
        /// <param name="key">
        /// The key.
        /// </param>
        object IDictionary.this[object key]
        {
            get
            {
                Guard.ArgumentNull("key", key);
                return key is TKey ? (object)this[(TKey)key] : null;
            }

            set
            {
                this[Guard.ArgumentNullOrWrongType<TKey>("key", key)] =
                    Guard.ArgumentWrongType<TValue>("value", value);
            }
        }

        bool IDictionary.Contains(object key)
        {
            Guard.ArgumentNull("key", key);
            return key is TKey && ContainsKey((TKey)key);
        }

        void IDictionary.Add(object key, object value)
        {
            this.Add(Guard.ArgumentNullOrWrongType<TKey>("key", key),
                Guard.ArgumentWrongType<TValue>("value", value));
        }

        ICollection IDictionary.Keys
        {
            get { return _keys ?? (_keys = new KeyCollection(this)); }
        }

        void ICollection.CopyTo(Array array, int arrayIndex)
        {
            CollectionGuard.CopyToInvalidArguments(array, arrayIndex, Count);

            // KeyValuePair array?
            var keyValueArray = array as KeyValuePair<TKey, TValue>[];
            if (keyValueArray != null)
            {
                this.CopyTo(keyValueArray, arrayIndex);
                return;
            }

            // DictionaryEntry array?
            var dictionaryEntryArray = array as DictionaryEntry[];
            if (dictionaryEntryArray != null)
            {
                this.CopyTo(dictionaryEntryArray, arrayIndex,
                    entry => new DictionaryEntry(entry.Key, entry.Value));
                return;
            }

            // Object array, copy as KeyValuePair.
            var objectArray = array as object[];
            if (objectArray != null)
            {
                try
                {
                    CopyTo(objectArray, arrayIndex,
                        entry => new KeyValuePair<TKey, TValue>(entry.Key, entry.Value));
                }
                catch
                {
                    // TODO: Throw
                }

                return;
            }
        }

        IDictionaryEnumerator IDictionary.GetEnumerator()
        {
            return new DictionaryEnumerator(this);
        }

        #endregion

        #region IDictionary<TKey,TValue> Members

        /// <summary>
        /// Determins whether the HashMap contains a specified key.
        /// </summary>
        /// <param name="key">
        /// The key to locate in the HashMap. This parameter may be null.
        /// </param>
        /// <returns>
        /// <b>true</b> if the hash table contains an element with the specified key; otherwise, <b>false</b>.
        /// </returns>
        public virtual bool ContainsKey(TKey key)
        {
            return FindEntry(key) != null;
        }

        /// <summary>
        /// Gets a value indicating whether this instance is read only.
        /// </summary>
        /// <value><c>true</c> if this instance is read only; otherwise, <c>false</c>.</value>
        public virtual bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Gets the enumerator.
        /// </summary>
        /// <returns>
        /// A <see cref="IEnumerator{KeyValuePair&lt;TKey, TValue&gt;}"/>
        /// </returns>
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            var enumerator = new Enumerator(this);
            while (enumerator.MoveNext())
            {
                var current = enumerator.Current;
                yield return new KeyValuePair<TKey, TValue>(current.Key, current.Value);
            }
        }

        /// <summary>
        /// Gets the value associated with the specified key.
        /// </summary>
        /// <param name="key">
        /// The key.
        /// </param>
        /// <param name="value">
        /// The value.
        /// </param>
        /// <returns>
        /// <c>true</c> if the <see cref="IDictionary{TKey, TValue}"/> contains an element with the 
        /// specified key; otherwise, false. 
        /// </returns>
        public bool TryGetValue(TKey key, out TValue value)
        {
            var entry = FindEntry(key);
            if (entry != null)
            {
                value = entry.Value;
                return true;
            }

            value = default(TValue);
            return false;
        }

        /// <summary>
        /// Gets or sets the <see cref="TValue"/> with the specified key.
        /// </summary>
        /// <value>The value.</value>
        public TValue this[TKey key]
        {
            get
            {
                var entry = FindEntry(key);
                if (entry == null)
                {
                    throw CollectionExceptions.KeyNotFound();
                }

                return entry.Value;
            }
            set
            {
                if (IsReadOnly)
                {
                    throw new NotSupportedException("The dictionary is read only.");
                }

                if (IsFixedSize)
                {
                    throw new NotSupportedException("The dictionary is fixed in size.");
                }

                InternalAdd(key, value, false);
            }
        }

        /// <summary>
        /// The add.
        /// </summary>
        /// <param name="item">
        /// The item.
        /// </param>
        void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item)
        {
            Add(item.Key, item.Value);
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item)
        {
            var entry = FindEntry(item.Key);
            return entry != null && EqualityComparer<TValue>.Default.Equals(entry.Value, item.Value);
        }

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            CollectionGuard.CopyToInvalidArguments(array, arrayIndex, Count);

            // copy items
            var index = arrayIndex;
            foreach (var keyValuePair in this)
            {
                array[index++] = keyValuePair;
            }

            // Dictionaries that filter out items (WeakHashMap, etc.) may not fully populate the array
            Array.Clear(array, index, Count - (index - arrayIndex));
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item)
        {
            var entry = FindEntry(item.Key);
            return EqualityComparer<TValue>.Default.Equals(entry.Value, item.Value) && Remove(entry.Key);
        }

        public void Clear()
        {
            ResetCapacity(0);
            _version++;
            Count = 0;
        }

        public ICollection<TKey> Keys
        {
            get { return _keys ?? (_keys = new KeyCollection(this)); }
        }

        public ICollection<TValue> Values
        {
            get { return _values ?? (_values = new ValueCollection(this)); }
        }

        public void Add(TKey key, TValue value)
        {
            if (IsReadOnly)
            {
                throw new NotSupportedException("The dictionary is read only.");
            }

            if (IsFixedSize)
            {
                throw new NotSupportedException("The dictionary is fixed in size.");
            }

            InternalAdd(key, value, true);
        }

        public bool Remove(TKey key)
        {
            if (IsReadOnly)
            {
                throw new NotSupportedException("The dictionary is read only.");
            }

            if (IsFixedSize)
            {
                throw new NotSupportedException("The dictionary is fixed in size.");
            }

            return InternalRemove(key);
        }

        public int Count { get; private set; }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        private void ResetCapacity(int capacity)
        {
            this._buckets = capacity != 0 ? new Entry[Primes.NextPrime(capacity)] : EmptyArray<Entry>.Instance;
        }

        private void CopyTo<T>(T[] array, int arrayIndex, Func<Entry, T> selector)
        {
            var enumerator = new Enumerator(this);

            var index = arrayIndex;
            while (enumerator.MoveNext())
            {
                array[index++] = selector(enumerator.Current);
            }

            // Dictionaries that filter out items (WeakHashMap, etc.) may not fully populate the array
            Array.Clear(array, index, Count - (index - arrayIndex));
        }

        protected void InternalAdd(IDictionary<TKey, TValue> dictionary)
        {
            if (dictionary == null)
            {
                return;
            }

            var sourceMap = dictionary as HashMap<TKey, TValue>;
            if (sourceMap != null)
            {
                InternalAdd(new Enumerator(sourceMap));
            }
            else
            {
                foreach (var entry in dictionary)
                {
                    // Ignore, IsFixedSize and IsReadOnly for internal adds.
                    InternalAdd(entry.Key, entry.Value, true);
                }
            }
        }

        protected void InternalAdd(Enumerator enumerator)
        {
            if (enumerator == null)
            {
                return;
            }

            while (enumerator.MoveNext())
            {
                var entry = enumerator.Current;

                // Ignore, IsFixedSize and IsReadOnly for internal adds.
                InternalAdd(entry.Key, entry.Value, true);
            }
        }

        protected virtual bool KeysEqual(TKey key1, TKey key2)
        {
            return EqualityComparer.Equals(key1, key2);
        }

        /// <summary>
        /// Hashes the specified key.
        /// </summary>
        /// <param name="key">The key.</param>
        /// <returns></returns>
        protected int Hash(TKey key)
        {
            return Hash(key, Capacity);
        }

        /// <summary>
        /// Returns a valid hashcode for the key within the HashMaps capacity
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="bucketCount">The table Size.</param>
        /// <returns>The hash.</returns>
        protected int Hash(TKey key, int bucketCount)
        {
            return Math.Abs(((_equalityComparer != null) ? _equalityComparer.GetHashCode(key) : key.GetHashCode())) %
                   bucketCount;
        }

        /// <summary>
        /// Determines whether the HashMap contains a specific value.
        /// </summary>
        /// <param name="value">
        /// The value to locate in the HashMap. This parameter may be null.
        /// </param>
        /// <returns>
        /// <b>true</b> if the hash table contains an element with the specified value; otherwise, <b>false</b>.
        /// </returns>
        public virtual bool ContainsValue(TValue value)
        {
            var comparer = EqualityComparer<TValue>.Default;

            var enumerator = new Enumerator(this);
            while (enumerator.MoveNext())
            {
                if (enumerator.Current.IsAlive && comparer.Equals(enumerator.Current.Value, value))
                {
                    return true;
                }
            }

            return false;
        }

        private Entry FindEntry(TKey key, out int bucketIndex)
        {
            if (Capacity > 0)
            {
                bucketIndex = Hash(key);
                return FindEntryInBucket(bucketIndex, key);
            }

            bucketIndex = -1;
            return null;
        }

        protected void InternalAdd(TKey key, TValue value, bool isAdd)
        {
            int bucketIndex;

            var entry = FindEntry(key, out bucketIndex);
            if (entry != null)
            {
                if (isAdd)
                {
                    throw CollectionExceptions.DuplicateKey("key");
                }

                OnSet(entry);
                entry.Value = value;
                _version++;
                OnSetComplete(entry);
            }
            else
            {
                entry = NewEntry(key, value);
                OnAdd(entry);

                if (Resize())
                {
                    bucketIndex = Hash(key, _buckets.Length);
                }

                entry.Next = _buckets[bucketIndex];
                _buckets[bucketIndex] = entry;

                _version++;
                Count++;

                OnAddComplete(entry);
            }
        }

        private Entry FindEntryInBucket(int bucketIndex, TKey key)
        {
            Entry entry;
            for (entry = this._buckets[bucketIndex]; entry != null; entry = entry.Next)
            {
                // Is it our entry?
                if (KeysEqual(entry.Key, key))
                {
                    return entry;
                }
            }

            return null;
        }

        private bool Resize()
        {
            if (Math.Floor(this._buckets.Length * LoadFactor) > Count)
            {
                return false;
            }

            var saveCount = Count;

            OnResize();

            // We may have freed up enough space in the OnResize
            var resize = Count == 0 || saveCount - Count < (int)(saveCount * 0.25);
            if (resize)
            {
                Rehash(Primes.NextPrime(Capacity * 2), LoadFactor);
            }

            OnResizeComplete();
            return resize;
        }

        protected bool InternalRemove(TKey key)
        {
            if (Count == 0)
            {
                return false;
            }

            var tableIndex = Hash(key, this._buckets.Length);
            for (Entry current = this._buckets[tableIndex], previous = null; current != null; previous = current, current = current.Next)
            {
                if (KeysEqual(current.Key, key))
                {
                    OnRemove(current);

                    // remove item
                    if (previous != null)
                    {
                        previous.Next = current.Next;
                    }
                    else
                    {
                        this._buckets[tableIndex] = current.Next;
                    }

                    current.Next = null;
                    _version++;
                    Count--;
                    OnRemoveComplete(current);
                    return true;
                }
            }

            // No entry found
            return false;
        }

        /// <summary>
        /// Returns a new HashEntry for the specified key / value pair.
        /// </summary>
        /// <param name="key">
        /// The entries key.
        /// </param>
        /// <param name="value">
        /// The entries value.
        /// </param>
        /// <returns>
        /// A new HashEntry instance.
        /// </returns>
        /// <remarks>
        /// Descendents may override this method, the default implementation returns
        /// a new BasicEntry instance.
        /// </remarks>
        protected virtual Entry NewEntry(TKey key, TValue value)
        {
            return new DefaultEntry(key, value);
        }

        /// <summary>
        /// The find.
        /// </summary>
        /// <param name="key">
        /// The key.
        /// </param>
        /// <returns>
        /// </returns>
        protected Entry FindEntry(TKey key)
        {
            return Count != 0 ? FindEntryInBucket(Hash(key, this._buckets.Length), key) : null;
        }

        /// <summary>
        /// The rehash.
        /// </summary>
        /// <param name="newCapacity">
        /// The new capacity.
        /// </param>
        /// <param name="newLoadFactor">
        /// The new load factor.
        /// </param>
        /// <exception cref="ArgumentOutOfRangeException">
        /// </exception>
        /// <exception cref="ArgumentOutOfRangeException">
        /// </exception>
        protected void Rehash(int newCapacity, double newLoadFactor)
        {
            // Check load factor.
            if (newLoadFactor < 0.1)
            {
                throw new ArgumentOutOfRangeException("newLoadFactor", "Load factor must be >= 0.1");
            }

            if (newLoadFactor > 1.0)
            {
                throw new ArgumentOutOfRangeException("newLoadFactor", "Load factor must be less than < 1.0");
            }

            // Set the new load factor
            LoadFactor = newLoadFactor;

            // Ensure the new capacity is in range for the specified load factor.
            var minCapacity = (int)(Count / LoadFactor);
            if (newCapacity < minCapacity)
            {
                newCapacity = Primes.NextPrime(minCapacity);
            }

            // Allocate new table
            var newTable = new Entry[newCapacity];

            for (int i = 0, j = 0; (i < this._buckets.Length) && (j < Count); i++)
            {
                var c = this._buckets[i];
                while (c != null)
                {
                    var tableIndex = Hash(c.Key, newCapacity);

                    // Save next
                    var n = c.Next;

                    // Replace head node
                    c.Next = newTable[tableIndex];
                    newTable[tableIndex] = c;

                    c = n;

                    // Increment count check, i.e. stop iterating when count is reached.
                    j++;
                }
            }

            // Assign new table
            this._buckets = newTable;
        }

        #region Notification Methods, OnAdd, etc...

        /// <summary>
        /// Called when a remove operation is about to occur.
        /// </summary>
        /// <param name="entry">
        /// The entry being removed.
        /// </param>
        protected virtual void OnRemove(Entry entry)
        {
        }

        /// <summary>
        /// Called when a remove operation has completed.
        /// </summary>
        /// <param name="entry">
        /// The removed entry.
        /// </param>
        protected virtual void OnRemoveComplete(Entry entry)
        {
        }

        /// <summary>
        /// Called when a set operation is about to occur.
        /// </summary>
        /// <param name="entry">
        /// The entry.
        /// </param>
        protected virtual void OnSet(Entry entry)
        {
        }

        /// <summary>
        /// Called when a set operation has completed.
        /// </summary>
        /// <param name="entry">The entry.</param>
        protected virtual void OnSetComplete(Entry entry)
        {
        }

        /// <summary>
        /// Called when an add operation is about to occur.
        /// </summary>
        /// <param name="entry">
        /// The entry.
        /// </param>
        protected virtual void OnAdd(Entry entry)
        {
        }

        /// <summary>
        /// Called when an add operation has completed.
        /// </summary>
        /// <param name="entry">
        /// The entry.
        /// </param>
        protected virtual void OnAddComplete(Entry entry)
        {
        }

        /// <summary>
        /// Called when a resize operation is about to occur.
        /// </summary>
        protected virtual void OnResize()
        {
        }

        /// <summary>
        /// Called when a resize operation has completed.
        /// </summary>
        protected virtual void OnResizeComplete()
        {
        }

        #endregion
    }
}